#include <stdafx.h>
#include <memory.h>

unsigned int tab1[] = {
	0xa0000000, 0x00000002, 0x60000000, 0x00000006,
	0x40000000, 0x0000000a, 0x20000000, 0x00000012,
	0x12000000, 0x00000019, 0x0c000000, 0x0000001f,
	0x07000000, 0x00000029, 0x03000000, 0x00000039,
	0x01600000, 0x00000046, 0x00f00000, 0x0000004d,
	0x00c00000, 0x00000053, 0x00b00000, 0x00000057,
	0x00a00000, 0x0000005f, 0x00000000, 0x000000ff
};
unsigned char tab2[] = {
	0x08, 0x09, 0x0A, 0x00, 0x07, 0x0B, 0x0C, 0x06, 0x29, 0x2A, 0xE0, 0x04, 0x05, 0x20, 0x28, 0x2B,
	0x2C, 0x40, 0x4A, 0x03, 0x0D, 0x25, 0x26, 0x27, 0x48, 0x49, 0x24, 0x47, 0x4B, 0x4C, 0x69, 0x6A,
	0x23, 0x46, 0x60, 0x63, 0x67, 0x68, 0x88, 0x89, 0xA0, 0xE8, 0x01, 0x02, 0x2D, 0x43, 0x44, 0x45,
	0x65, 0x66, 0x80, 0x87, 0x8A, 0xA8, 0xA9, 0xC0, 0xC9, 0xE9, 0x0E, 0x4D, 0x64, 0x6B, 0x6C, 0x84,
	0x85, 0x8B, 0xA4, 0xA5, 0xAA, 0xC8, 0xE5, 0x83, 0x86, 0xA6, 0xA7, 0xC7, 0xCA, 0xE7, 0x22, 0x2E,
	0x8C, 0xC4, 0xE4, 0xE6, 0x4E, 0x6D, 0xC6, 0xEC, 0x0F, 0x10, 0x11, 0x8D, 0xAB, 0xAC, 0xCC, 0xEA,
	0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, 0x1A, 0x1B, 0x1C, 0x1D, 0x1E, 0x1F, 0x21, 0x2F,
	0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x3A, 0x3B, 0x3C, 0x3D, 0x3E, 0x3F, //tab3
	0x41, 0x42, 0x4F, 0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x57, 0x58, 0x59, 0x5A, 0x5B, 0x5C,
	0x5D, 0x5E, 0x5F, 0x61, 0x62, 0x6E, 0x6F, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78,
	0x79, 0x7A, 0x7B, 0x7C, 0x7D, 0x7E, 0x7F, 0x81, 0x82, 0x8E, 0x8F, 0x90, 0x91, 0x92, 0x93, 0x94,
	0x95, 0x96, 0x97, 0x98, 0x99, 0x9A, 0x9B, 0x9C, 0x9D, 0x9E, 0x9F, 0xA1, 0xA2, 0xA3, 0xAD, 0xAE,
	0xAF, 0xB0, 0xB1, 0xB2, 0xB3, 0xB4, 0xB5, 0xB6, 0xB7, 0xB8, 0xB9, 0xBA, 0xBB, 0xBC, 0xBD, 0xBE,
	0xBF, 0xC1, 0xC2, 0xC3, 0xC5, 0xCB, 0xCD, 0xCE, 0xCF, 0xD0, 0xD1, 0xD2, 0xD3, 0xD4, 0xD5, 0xD6,
	0xD7, 0xD8, 0xD9, 0xDA, 0xDB, 0xDC, 0xDD, 0xDE, 0xDF, 0xE1, 0xE2, 0xE3, 0xEB, 0xED, 0xEE, 0xEF,
	0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7, 0xF8, 0xF9, 0xFA, 0xFB, 0xFC, 0xFD, 0xFE, 0xFF,
	//0x100
	0x00, 0x00, 0x01, 0x00, 0x02, 0x00, 0x03, 0x00, 0x04, 0x00, 0x06, 0x00, 0x08, 0x00, 0x0C, 0x00, //tab6
	0x10, 0x00, 0x18, 0x00, 0x20, 0x00, 0x30, 0x00, 0x40, 0x00, 0x60, 0x00, 0x80, 0x00, 0xC0, 0x00, 
	0x00, 0x01, 0x80, 0x01, 0x00, 0x02, 0x00, 0x03, 0x00, 0x04, 0x00, 0x06, 0x00, 0x08, 0x00, 0x0C, 
	0x00, 0x10, 0x00, 0x18, 0x00, 0x20, 0x00, 0x30, 0x00, 0x40, 0x00, 0x60, 
	//0x13c
	0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x0A, 0x0C, 0x0E, 0x10, 0x14, 0x18, 0x1C, //tab4
	0x20, 0x28, 0x30, 0x38, 0x40, 0x50, 0x60, 0x70, 0x80, 0xA0, 0xC0, 0xE0, 0xFF, 0x00, 0x00, 0x00, 
	//0x15c
	0x00, 0x00, 0x00, 0x00, 0x01, 0x01, 0x02, 0x02, 0x03, 0x03, 0x04, 0x04, 0x05, 0x05, 0x06, 0x06, //tab5
	0x07, 0x07, 0x08, 0x08, 0x09, 0x09, 0x0A, 0x0A, 0x0B, 0x0B, 0x0C, 0x0C, 0x0D, 0x0D, 0x0E, 0x0E,
	//0x17c
	0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x01, 0x01, 0x01, 0x02, 0x02, 0x02, 0x02,
	0x03, 0x03, 0x03, 0x03, 0x04, 0x04, 0x04, 0x04, 0x05, 0x05, 0x05, 0x05, 0x00, 0x00, 0x00, 0x00,
};
unsigned char tab5[] = {
	0x00, 0x00, 0x00, 0x00, 0x01, 0x01, 0x02, 0x02, 0x03, 0x03, 0x04, 0x04, 0x05, 0x05, 0x06, 0x06,
	0x07, 0x07, 0x08, 0x08, 0x09, 0x09, 0x0A, 0x0A, 0x0B, 0x0B, 0x0C, 0x0C, 0x0D, 0x0D, 0x0E, 0x0E
};
unsigned short tab6[] = {
	0x0000, 0x0001, 0x0002, 0x0003, 0x0004, 0x0006, 0x0008, 0x000c,
	0x0010, 0x0018, 0x0020, 0x0030, 0x0040, 0x0060, 0x0080, 0x00c0,
	0x0100, 0x0180, 0x0200, 0x0300, 0x0400, 0x0600, 0x0800, 0x0c00,
	0x1000, 0x1800, 0x2000, 0x3000, 0x4000, 0x6000
};
unsigned char *tab3 = &tab2[0x7c];
unsigned char *tab4 = &tab2[0x13c];


class Decompress
{
public:
	struct HuffmanData {
		unsigned int data[0x200];
		unsigned int dataHelper1[0x48];
		unsigned int dataHelper2[0x200];
	};
	struct {
		unsigned int *pInput;
		int inputSize;
		unsigned char *pOutput;
		int outputSize;
		//10
		int currentUncompressedSize;
		int totalUncompressedSize;
		unsigned int state;
		unsigned int iterator;
		//20
		unsigned int readChunk1;
		unsigned int readChunk2;
		unsigned int readCount;
		unsigned int _2c;
		unsigned int _30;
		unsigned int writeChunk1;
		unsigned int writeChunk2;
		unsigned int _3c;
		unsigned int _40[0x2000];
		unsigned int _8040;
		HuffmanData huffmanData1;
		HuffmanData huffmanData2;
		//a284
		unsigned int totalSymbolCount;
		unsigned int _a288[0x20];
		unsigned int _a308[0x20];
		unsigned int tempBuffer[0x10000];
		unsigned int symbolCount;
		unsigned char *outBuffer;
		
	} state;

	unsigned char* DecompressFile(unsigned int* pInput, int inputSize, int &outputSize)
	{
		if (!pInput) {
			return NULL;
		}

		unsigned int bitCount, writeLoc, writeSize;

		memset(&state, 0, sizeof(state));
		state.pInput = &pInput[2];
		state.inputSize = inputSize - 3*sizeof(unsigned int);
		state.totalUncompressedSize = outputSize = pInput[1];
		state.outBuffer = new unsigned char[state.totalUncompressedSize];
		state.pOutput = &state.outBuffer[0];
		state.outputSize = 0x10000;
		memset(state.outBuffer, 0, state.totalUncompressedSize);

		if (state.totalUncompressedSize > 0x10000) {
			delete [] state.outBuffer;
			return NULL;
		}

		unsigned int orgSize = state.outputSize;

		while (state.state < 0xd)
		{
			switch (state.state) {
			case 0x0:
				readChunk(0x8);

				state.readChunk2 = (state.readChunk2 << 4) | (state.readChunk1 >> (32 - 4));
				state.readChunk1 = state.readChunk1 << 4;
				state._2c = (state.readChunk2 >> 0x1c) + 1;
				state.readChunk2 = (state.readChunk2 << 4) | (state.readChunk1 >> (32 - 4));
				state.readChunk1 = state.readChunk1 << 4;
				state.readCount -= 0x8;

				state.state = 0x1;


			case 0x1:
				if (!setupHuffmanData(&state.huffmanData1) || !setupHuffmanData(&state.huffmanData2)) {
					break;
				}
				
				state.state = 0x5;


			case 0x5:
				readChunk(0x4);

				state._30 = ((state.readChunk2 >> 0x1c) + 1) << 0xc;
				state.readChunk2 = (state.readChunk2 << 4) | (state.readChunk1 >> (32 - 4));
				state.readChunk1 = state.readChunk1 << 0x4;
				state.readCount -= 0x4;

				state.state = 0x6;


			case 0x6:
				if (!state._30) {
					state.state = 0x1;
					continue;
				}
				if (state.currentUncompressedSize == state.totalUncompressedSize) {
					state.state = 0xc;
					continue;
				}

				processTree(&state.huffmanData1, state.writeChunk1);
				state._30--;

				if (state.writeChunk1 < 0x100) {
					state.state = 0xb;
					continue;
				}

				
				bitCount = tab3[state.writeChunk1];
				if (bitCount) {
					if (bitCount > 0x20) {
						goto cancelProc;
					}
					readChunk(bitCount);
					state.writeChunk1 = tab4[state.writeChunk1 - 0x100] | shiftChunksRight(state.readChunk1, state.readChunk2, 0x40 - bitCount);

					state.readCount -= bitCount;
					shiftChunksLeft(state.readChunk1, state.readChunk2, bitCount);
				} else {
					state.writeChunk1 = tab4[state.writeChunk1 - 0x100];
				}
				state.writeChunk1 += state._2c;

				
				processTree(&state.huffmanData2, state.writeChunk2);

				
				bitCount = tab5[state.writeChunk2];
				if (bitCount) {
					if (bitCount > 0x20) {
						goto cancelProc;
					}
					readChunk(bitCount);
					state.writeChunk2 = tab6[state.writeChunk2] | shiftChunksRight(state.readChunk1, state.readChunk2, 0x40 - bitCount);

					state.readCount -= bitCount;
					shiftChunksLeft(state.readChunk1, state.readChunk2, bitCount);
				} else {
					state.writeChunk2 = tab6[state.writeChunk2];
				}
				state.writeChunk2++;

				state.state = 0xa;


			case 0xa:
				if (state.outputSize == 0 || state.currentUncompressedSize >= state.totalUncompressedSize) {
					//copy
					return state.outBuffer;
				}
				writeLoc = orgSize - state.outputSize;
				if (writeLoc >= state.writeChunk2) {
					writeLoc = (unsigned int)state.pOutput - state.writeChunk2;
					writeSize = state.writeChunk1;
				} else {
					writeSize = state.writeChunk2 - writeLoc;
					writeLoc = state._8040;
					if (writeSize > writeLoc) {
						writeSize -= writeLoc;
						writeLoc = (unsigned int)&state - writeSize + 0x803c;
					} else {
						writeLoc = (unsigned int)&state + (writeLoc - writeSize) + 0x3c;
					}
					if (writeSize >= state.writeChunk1) {
						writeSize = state.writeChunk1;
					}
				}
				if (writeSize >= (unsigned int)state.outputSize) {
					writeSize = state.outputSize;
				}
				state.writeChunk1 -= writeSize;
				state.currentUncompressedSize += writeSize;
				state.outputSize -= writeSize;
				for (; writeSize > 0; writeSize--) {
					*state.pOutput = *(unsigned char *)writeLoc;
					state.pOutput++;
					writeLoc++;
				}
				if (state.writeChunk1 == 0) {
					state.state = 0x6;
					continue;
				} else {
					continue;
				}


			case 0xb:
				if (state.outputSize == 0) {
					//copy!!!
					return state.outBuffer;
				}

				*state.pOutput = (unsigned char)state.writeChunk1;
				state.pOutput++;
				state.outputSize--;
				state.currentUncompressedSize++;

				state.state = 0x6;
				continue;


			case 0xc:
				if (state.inputSize <= 0) {
					//SUCCESS!
					return state.outBuffer;
				} else {
					break;
				}
			}

			//break breaks out of switch and lands here. this breaks while too
			state.state = 0xd;
		}

	cancelProc:
		delete [] state.outBuffer;
		return NULL;
	}

	void processTree(HuffmanData *huffdata, unsigned int &writeChunk)
	{
		readChunk(0x20);

		unsigned int bitCount = huffdata->data[(state.readChunk2 >> 0x18)*2];
		unsigned int treeValue = huffdata->data[(state.readChunk2 >> 0x18)*2 + 1];
		if (bitCount == -1) {
			int i = 0;
			while (state.readChunk2 < huffdata->dataHelper1[i]) {
				i += 3;
			}
			bitCount = huffdata->dataHelper1[i+2];
			treeValue = huffdata->dataHelper1[i+1] - ((state.readChunk2 - huffdata->dataHelper1[i]) >> (0x20 - bitCount));
			treeValue = huffdata->dataHelper2[treeValue];
		}

		state.readCount -= bitCount;
		shiftChunksLeft(state.readChunk1, state.readChunk2, bitCount);
		writeChunk = treeValue;
	}
	bool setupHuffmanData(HuffmanData *huffdata)
	{
		readChunk(0x10);

		state.totalSymbolCount = (state.readChunk2 >> 0x10) & 0xffff;
		state.iterator = state.totalSymbolCount - 1;
		state.symbolCount = 0;
		memset(state._a288,0,0x80);
		memset(state._a308,0xff,0x80);

		state.readChunk2 = (state.readChunk2 << 16) | (state.readChunk1 >> (32 - 16));
		state.readChunk1 = state.readChunk1 << 0x10;
		state.readCount -= 0x10;

		while (state.iterator != -1) {
			readChunk(0x20);

			int i = 0;
			while (state.readChunk2 < tab1[i]) {
				i += 2;
			}

			int j = (i*4 + 0x18) >> 3;
			unsigned char bitCount = tab2[tab1[i+1] - ((state.readChunk2 - tab1[i]) >> (0x20 - j))];
			state.readCount -= j;
			shiftChunksLeft(state.readChunk1, state.readChunk2, j);
			j = bitCount >> 5;
			bitCount &= 0x1f;
			if (bitCount > 0x1f) { //CMP_MAX_ENCODED_BITS
				return false;
			}
			if ((unsigned int)j > state.iterator) {
				return false;
			}
			if (bitCount || state.totalSymbolCount < 2) {
				state._a288[bitCount] += j + 1;
				state.symbolCount += j + 1;
				do {
					if (state.iterator >= state.totalSymbolCount) {
						return false;
					}
					state.tempBuffer[state.iterator] = state._a308[bitCount];
					state._a308[bitCount] = state.iterator;
					state.iterator--;
					j--;
				} while (state.iterator != -1 && j != -1);
			} else {
				state.iterator -= j + 1;
			}
		}

		if (state.totalSymbolCount && !state.symbolCount) {
			state.tempBuffer[state.totalSymbolCount-1] = state._a308[0];
			state._a308[0] = state.totalSymbolCount-1;
			state._a288[0] = 1;
			state.symbolCount = 1;
		}

		unsigned int loc2 = 0;
		unsigned int loc3 = 0;
		unsigned int loc4 = (unsigned int)&state._a308[0];
		unsigned int loc5 = 8;
		unsigned int loc6 = 0;

		do {
			unsigned int treeVal = *(unsigned int *)loc4;
			if (treeVal != -1) {
				do {
					if (loc6 >= (unsigned int)(1 << loc3) || treeVal >= state.totalSymbolCount) {
						return false;
					}

					int i = 1 << loc5;
					if (i) {
						do {
							i--;
							unsigned int hashSlot = (loc6 << (8 - loc3)) | i;
							if (hashSlot >= 0x100) { //HASH_SIZE
								return false;
							}
							huffdata->data[hashSlot*2] = loc3;
							huffdata->data[hashSlot*2+1] = treeVal;
						} while (i);
					}
					treeVal = state.tempBuffer[treeVal];
					loc2++;
					loc6--;
				} while (treeVal != -1);
			}
			loc4 += 4;
			loc5--;
			loc3++;
			loc6 = 2*loc6 + 1;
		} while (loc3 <= 8);

		if (loc2 > state.symbolCount) {
			return false;
		}

		if (loc2 != state.symbolCount) {
			if ((state.symbolCount - loc2) > 0x200) {
				return false;
			}
			unsigned int counter = 0;
			if (loc3 <= 0x1f) {
				loc5 = loc3 - 8;
				loc4 = (unsigned int)&huffdata->dataHelper1[2];
				unsigned int ptr = (unsigned int)&state._a308[loc3];
				do {
					unsigned int treeVal = *(unsigned int *)ptr;
					if (treeVal != -1) {
						do {
							if (loc6 >= (unsigned int)(1 << loc3) || treeVal >= state.totalSymbolCount) {
								return false;
							}
							huffdata->data[(loc6 >> loc5)*2] = -1;
							loc6--;
							counter++;
							huffdata->dataHelper2[counter-1] = treeVal;
							treeVal = state.tempBuffer[treeVal];
						} while (treeVal != -1);
						unsigned int *write = (unsigned int *)loc4;
						write[0] = loc3;
						write[-1] = counter-1;
						write[-2] = (loc6+1) << (0x20 - loc3);
						loc4 += 0x0c;
					}
					ptr += 4;
					loc5++;
					loc3++;
					loc6 = 2*loc6 + 1;
				} while (loc3 <= 0x1f);
			}
		}

		return true;
	}
	void readChunk(unsigned int bitCount)
	{
		if (state.readCount < bitCount && state.inputSize >= 4)
		{
			unsigned int data = state.pInput[0];
			state.pInput++;
			state.inputSize -= sizeof(unsigned int);

			unsigned int shiftVal = 0;
			shiftChunksLeft(data, shiftVal, 0x20 - state.readCount);
			state.readChunk1 |= data;
			state.readChunk2 |= shiftVal;
			state.readCount += 0x20;
		}
	}
	void shiftChunksLeft(unsigned int &chunkpart1, unsigned int &chunkpart2, unsigned int shift)
	{
		if (shift >= 0x40) {
			chunkpart1 = 0;
			chunkpart2 = 0;
		} else if (shift >= 0x20) {
			chunkpart2 = chunkpart1;
			chunkpart1 = 0;
			chunkpart2 <<= shift & 0x1f;
		} else {
			chunkpart2 = (chunkpart2 << shift) | (chunkpart1 >> (32 - shift));
			chunkpart1 <<= shift;
		}
	}
	unsigned int shiftChunksRight(unsigned int chunkpart1, unsigned int chunkpart2, unsigned int shift)
	{
		if (shift >= 0x40) {
			return 0;
		} else if (shift >= 0x20) {
			return chunkpart2 >> (shift & 0x1f);
		} else {
			return (chunkpart1 >> shift) | (chunkpart2 << (32 - shift)); //SHRD
		}
	}

};

void UnpackGWDat(unsigned char *input, int insize, unsigned char *&output, int &outsize)
{
	Decompress d;
	output=d.DecompressFile((unsigned int*)input,insize,outsize);
}